# 20.有效的括号
# 给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s ，判断字符串是否有效。
#
# 有效字符串需满足：
# 左括号必须用相同类型的右括号闭合。
# 左括号必须以正确的顺序闭合。
# 每个右括号都有一个对应的相同类型的左括号。
#
#
# 示例1：
# 输入：s = "()"
# 输出：true
#
# 示例2：
# 输入：s = "()[]{}"
# 输出：true
#
# 示例3：
# 输入：s = "(]"
# 输出：false


class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i in ['(','[,','{']:
                stack.append(i)
            elif i == ')' and stack and  stack[-1] == '(':
                stack.pop()
            elif i == ']' and stack and  stack[-1] == '[':
                stack.pop()
            elif i == '}' and stack and  stack[-1] == '{':
                stack.pop()
            else:
                return False
        if stack:
            return False
        else:
            return True

    # 这是我一年前写的答案，明明做出来了，还是得说一下这也行？！
    def isValid1(self, s: str) -> bool:
        a = "()"
        b = "[]"
        c = "{}"
        while a in s or b in s or c in s:
            s = s.replace(a,"")
            s = s.replace(b,"")
            s = s.replace(c,"")
        if s == "":
            return True
        else:
            return False

if __name__ == '__main__':
    s= "()"
    s= "([)][]"
    # s= "()[]{}"
    # s= "]"
    tmp = Solution()
    res = tmp.isValid1(s)
    print(res)
